package sort.leetcode;

public class SortListFastLow {
    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) {
            this.val = val;
        }
    }

    public static ListNode sortList(ListNode head) {
        if (head == null) {
            return null;
        }
        return mergeSortList(head, null); // 让tail为尾节点的下一个
    }

    /**
     *
     * @param head
     * @param tailNext 处理区间的下一个节点
     * @return
     */
    private static ListNode mergeSortList(ListNode head, ListNode tailNext) {
        if (head == null) {
            // 尾节点的最后一个直接返回空
            return null;
        }
        if (head.next == tailNext) {
            // 如果head的下一个就是处理区间的下一个节点，说明已经就剩一个节点了找到了终点
            // 将其与后一个节点断开，获得独立的节点
            head.next = null;
            return head;
        }
        // 寻找中间节点
        ListNode low = head, fast = head;
        while (fast != tailNext) {
            low = low.next;
            fast = fast.next;
            // 查看fast是否已经走到头
            if (fast != tailNext) {
                fast = fast.next;
            }
        }
        ListNode mid = low;
        ListNode list1 = mergeSortList(head, mid); // [low, mid)
        ListNode list2 = mergeSortList(mid, tailNext); // [mid, tailNext)
        ListNode curHead = merge(list1, list2);
        return curHead;
    }

    private static ListNode merge(ListNode list1, ListNode list2) {
        ListNode dummyHead = new ListNode(-100001);
        ListNode tmpNode = dummyHead;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                tmpNode.next = list1;
                list1 = list1.next;
            } else {
                tmpNode.next = list2;
                list2 = list2.next;
            }
            tmpNode = tmpNode.next;
        }
        if (list1 != null) {
            tmpNode.next = list1;
        } else if (list2 != null){
            tmpNode.next = list2;
        }
        return dummyHead.next;
    }

    public static void main(String[] args) {
        int[] nums = new int[] {-1, 5, 3, 4, 0};
        ListNode head = new ListNode(nums[0]);
        ListNode tmp = head;
        for (int i = 1; i < nums.length; i++) {
            tmp.next = new ListNode(nums[i]);
            tmp = tmp.next;
        }
        ListNode newHead = sortList(head);
        System.out.println();
    }
}
